/*
 * @lc app=leetcode.cn id=86 lang=javascript
 *
 * [86] 分隔链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function (head, x) {
  if (head === null) return head;

  const smallLink = new ListNode(-1, null);
  const largeLink = new ListNode(-1, null);
  let sp = smallLink;
  let lp = largeLink;

  let p = head;
  while (p) {
    let q = p.next;
    if (p.val < x) {
      p.next = sp.next;
      sp.next = p;
      sp = p;
    } else {
      p.next = lp.next;
      lp.next = p;
      lp = p;
    }
    p = q;
  }

  sp.next = largeLink.next;

  return smallLink.next;
};
// @lc code=end
